package Day2025_03_09;

import java.util.*;

public class LeetCode127 {
    public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        Set<String> vis = new HashSet<>();
        Set<String> hash = new HashSet<>();
        for (String str : wordList) hash.add(str);
        if (beginWord.equals(endWord)) return 1;
        if (!hash.contains(endWord)) return 0;
        Queue<String> q = new LinkedList<>();
        int step = 0;
        q.add(beginWord);
        vis.add(beginWord);
        while (!q.isEmpty()) {
            int sz = q.size();
            step++;
            while (sz-- != 0) {
                String t = q.poll();
                for (int i = 0; i < beginWord.length(); i++) {
                    char[] tmp = t.toCharArray();
                    for (char ch = 'a'; ch <= 'z'; ch++) {
                        tmp[i] = ch;
                        String next = new String(tmp);
                        if (!vis.contains(next) && hash.contains(next)) {
                            if (endWord.equals(next)) return step + 1;
                            q.add(next);
                            vis.add(next);
                        }
                    }
                }
            }
        }
        return 0;
    }
}
